/*
练习10-2 正负数分类
分数 20
作者 陈越
单位 浙江大学

给定一个整数序列，要求将序列中所有负数都放于所有非负数之前。
函数接口定义：

void Partition( ElemSet *a, int n );

函数接口定义中，ElemSet 是用户定义的数据类型，此处就定义为 int；序列元素存储在数组 a 中，可以是任意 int 范围内的整数；另一个参数 n 是数组 a 的长度，其值不超过 105。注意：数组下标从 0 开始。
函数 Partition 需要将 a 中的所有负数都放于所有非负数之前，并将调整后的序列仍然存在 a 中返回。注意：结果可能不唯一，返回任何一组正确的结果即可。

输入样例：

10
0 -1 1 2 -3 0 -4 -5 -6 0

输出样例：

1

样例说明：

分类后数组 a 有多种可能，函数 Judge 通过比较输入数据 input 和 a 来判定。
例如 [-1 -3 -4 -5 -6 0 0 1 2 0] 和 [-6 -1 -5 -4 -3 0 2 1 0 0] 都可以得到输出 1。
只有得到 Judge 输出 1 的结果才是正确的。

*/

#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 默认元素为整数*/
void Partition(ElemSet *a, int n);
int Judge(ElemSet *input, ElemSet *a, int n); /* 裁判实现，详情略 */

int main(void)
{
    ElemSet *a, *input;
    int n, i;
    
    scanf("%d", &n);
    a = (ElemSet *)malloc(sizeof(ElemSet) * n);
    input = (ElemSet *)malloc(sizeof(ElemSet) * n);
    for (i=0; i<n; i++) {
        scanf("%d", &a[i]);
        input[i] = a[i];
    }
    Partition(a, n);
    printf("%d", Judge(input, a, n)); /* Judge返回 1 表示正确，0 表示错误 */
    return 0;
}
/* 你的代码将被嵌在这里 */

void Partition(ElemSet *a, int n) {
    int i = 0, j = n - 1;
    while (i < j) {
        while (a[i] < 0) i++;
        while (a[j] >= 0) j--;
        if (i < j) {
            ElemSet tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
}
